/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import org.junit.Test;

/**
 * <p>
 * 查找递增有序数组的旋转数组的最小数字
 * 假设没有重复数字
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月21日
 */
public class FindMinimuminRotatedSortedArray {

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int min = nums[left];
        while(left<right){
            mid = left+(right-left)/2;
            min = Math.min(nums[left], min);
            if(nums[mid]==nums[left] && nums[mid] == nums[right]){
                //不确定最小值在哪一个部分，向前移动一格
                left++;
            }else if(nums[mid]>=nums[left]){
                //在右边进行查找
                left = mid+1;
                min = Math.min(nums[left], min);
            }else{
                //在左半部分进行查找哦
                min = Math.min(nums[mid], min);
                right = mid-1;
            }
        }
        return min;
    }
    @Test
    public void testCase(){
        int []nums = {1,2};
        int min = findMin(nums);
        System.out.println("min:"+min);
    }
    @Test
    public void testCase2(){
        int []nums = {3,4,5,6,1,2};
        int min = findMin(nums);
        System.out.println("min:"+min);
    }
    @Test
    public void testCase3(){
        int []nums = {2,1};
        int min = findMin(nums);
        System.out.println("min:"+min);
    }
}
